#include <iostream>
using namespace std;
#include <vector>


void Merge(int arr[], int left , int mid , int right)
{
  int temp[right - left + 1];

  int i = left;
  int j = mid + 1;
  int k = 0;

  while(i <= mid && j <= right)
  {
    if (arr[i] <= arr[j])
    {
      temp[k] = arr[i];
      i++;
    }
    else 
    {
      temp[k] = arr[j];
      j++;
    }

    k++;
  }

  while(i <= mid)
  {
    temp[k++] = arr[i++];
  }

  while(j <= right)
  {
    temp[k++] = arr[j++];
  }

  for (int i = left ; i <= right ; i++)
  {
    arr[i] = temp[i - left];
  }
}


void MergeSort(int arr[],int left , int right)
{
  if (left >= right)
  {
    return;
  }

  int mid = left + (right - left) / 2;
  
  MergeSort(arr , left , mid);
  MergeSort(arr , mid+1 , right);

  Merge(arr , left , mid , right);
  // sorted
}


int main()
{
  int arr[] = {10 , 6, 7, 1, 3, 9, 4, 2};
  MergeSort(arr , 0 , 7);

  for (int i = 0; i < 8; i++)
  {
    cout << arr[i] << "  " ;
  }

  cout << endl;
  return 0;
}
